# 78/100 贪心算法-跳跃游戏
# leetcode第55题: https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/25

from leetcode.test import test_function as tf
import json


def canJump(nums: list[int]) -> bool:
    n = len(nums)
    max_len = 0  # 表示最远可以达到的下标位置
    for i in range(n - 1):
        max_len = max(max_len, i + nums[i])  # 遍历数组中的每个元素, 更新最远可达的下标
        if max_len >= n - 1:  # 终点判断
            return True
        if max_len < i + 1:  # 最远可达下标无法到达下一个下标
            return False
    return max_len >= n - 1


def canJump_opt(nums: list[int]) -> bool:
    n = len(nums)
    right = 0  # 表示最远可以达到的下标
    for i in range(n):
        if i > right:
            return False
        right = max(right, i + nums[i])

    return True


if __name__ == '__main__':
    # with open("./data/n_greed1_lc121.data", "r") as file:
    #     str = file.readline().strip()
    #     jo = json.loads(str)
    inp = [{"nums": [2, 3, 1, 1, 4]}, {"nums": [3, 2, 1, 0, 4]}, {"nums": [2, 3, 1, 0, 4]}, {"nums": [0]},
           {"nums": [0, 2, 3]}, ]
    out = [True, False, True, True, False]

    tf(canJump, inp, out)
